package _interview100;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 84. 柱状图中最大的矩形
 */
public class No84 {
    public int largestRectangleArea(int[] heights) {
        int ans = 0;

        int[] ints = new int[heights.length + 2];
        System.arraycopy(heights, 0, ints, 1, heights.length);

        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < ints.length; i++) {
            while (!stack.isEmpty() && ints[stack.peek()] > ints[i]) {
                Integer pop = stack.pop();
                if (stack.isEmpty()) break;
                int h = ints[pop];
                int w = i - stack.peek() - 1;
                ans = Math.max(h * w, ans);
            }
            stack.push(i);
        }
        return ans;
    }
}
